package com.sfx.算法专题.位运算;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: sfx
 * Date: 2023-08-21
 * Time: 9:53
 */
public class Code_5_singleNumber3 {
    // 1. 先把所有元素全部异或一遍
    // 2. 找到最后一个不同的bit,也就是一个是0,一个是1
    // 3. 我们就可以把按照这一位来进行分为两组
    // 4. 因为是异或操作,说明对于这一位来说就这两个数字的位置的bit各不相同(一个0,一个1),其他数字都可以进行抵消掉
    // 因此才可以这样进行分组
    static class Solution {
        public int[] singleNumber(int[] nums) {
            int sum = 0;
            for(int num:nums){
                sum ^= num;
            }
            int lowb = sum &(-sum);
            int num1 = 0,num2 = 0;
            for(int num:nums){
                if((num&lowb) == 0)
                    num1 ^= num;
                else
                    num2 ^=num;
            }
            return new int[]{num1,num2};
        }
    }
}